#include "cintmath.h"

/**
 * gcd - finds greatest common divisor for two given integer numbers
 * @param n1
 * @param n2
 * @return greatest common divisor
 */
template <typename T>
T CIntMath<T>::gcd(T n1, T n2) {
  T tmp;
  while (n2 != 0) {
    tmp = n1 % n2;
    n1 = n2;
    n2 = tmp;
  }
  return n1;
}
//---------------------------------------------------------------------------

/**
 * lcm - finds lowest common multiplicant for two given integer numbers
 * @param n1
 * @param n2
 * @return lowest common multiplicant
 */
template <typename T>
T CIntMath<T>::lcm(T n1, T n2) {
  return (n1 * n2) / gcd(n1, n2);
}
//---------------------------------------------------------------------------

/**
 * pow - raises given integer base to given natural exponent
 * @param base
 * @param exp
 * @return base raised to exp
 */
template <typename T>
T CIntMath<T>::pow(T base, T exp) {
  return (T) ::pow(base, exp);
}
//---------------------------------------------------------------------------

/**
 * pow - raises given integer base to given natural exponent
 * @param base
 * @param exp
 * @return base na exp
 */
template <>
CBigInt CIntMath<CBigInt>::pow(CBigInt base, CBigInt exp) {

  // If exponent is not natural, return
  if (exp < 0) return 0;
  CBigInt res(1);
  
  // While exponent is greater than 0, multiply result by base and lower
  // exponent by one
  // If exponent is not prime, reduce number of iterations with:
  // a^(x * y) = (a^x)^y
  while (exp > 0) {
  	CBigInt tmp = findSmallestPrimeDivisor(exp);
    if (tmp != -1) {
      base = pow(base, exp / tmp);
      exp = tmp;
    }
    else {
      res *= base;
      exp--;
    }
  }
  return res;
}
//---------------------------------------------------------------------------

/**
 * eulerFunc - euler function for given number
 * @param num
 * @return result from euler function
 */
template <typename T>
T CIntMath<T>::eulerFunc(T num) {

  // Euler function
  //-------------------------------------------------------------------------
  // Eulerova function - Fi(num) gives number of numbers from set
  // {1,2 ... num} that are not commensurable (haven't gcd) with number num
  //-------------------------------------------------------------------------
  T c(0); 
  for (T i = 1; i <= num; i++) {
    if (gcd(i, num) == 1) c++;
  }
  return c;
}
//---------------------------------------------------------------------------

/**
 * isCongruent - checks whether given two numbers are congruent
 * @param n1
 * @param n2
 * @param m
 * @return true if n1 is congruent n2 (mod m)
 */
template <typename T>
bool CIntMath<T>::isCongruent(T n1, T n2, T m) {
  return (n1 % m) == (n2 % m);
}
//---------------------------------------------------------------------------

/**
 * findSmallestPrimeDivisor - finds smallest prime divisor
 * @param num
 * @return smallest prime number which dividing num
 */
template <typename T>
T CIntMath<T>::findSmallestPrimeDivisor(T num) {
  T tmp(CMath<T>::sqrt(num) + T(1)), i(1);
  while (++i < tmp) if (!(num % i)) return i;
  return T(-1);
}
//---------------------------------------------------------------------------

/**
 * fastExp - fast raising to power modulo m
 * @param base
 * @param num
 * @param m
 * @return base raised to num mod m
 */
template <typename T>
T CIntMath<T>::fastExp(T base, T num, T m) {

  // Russian Peasant Algorithm
  //-------------------------------------------------------------------------
  // Fast raising to power: Base^N (mod M)
  // for example: 12^10 (mod 23)

  // At first exponent must be represented as sum of powers with base 2 and
  // then divide base to multiplicands in the form base^(corresponding power
  // of 2)
  // for example: 12^10 = 12^(2^3 + 2^1) = 12^(8 + 2) = 12^8 * 12^2
  
  // Next we are subsequently taking multiplicands starting with multiplicand
  // with smallest power of 2 in exponent and ending with largest power of 2
  // In every step we calculate remainder after division of actual
  // multiplicand by number m, resulting remainder we use for next step
  // for example:
  // 12^2: 12^2 (mod 23) = 6
  // 12^4:  6^2 (mod 23) = 13
  // 12^8: 13^2 (mod 23) = 8
  
  // The result is remainder after division of product of partial remainders
  // (from each step) by number m
  // for example: 12^10 (mod 23) = 12^8 * 12^2 (mod 23) = 8*6 (mod 23) = 2
  //-------------------------------------------------------------------------
  
  T i(0), res(1);
    
  // While (num / 2^i) is greater than zero...
  while ((num >> i) > 0) {
  
    // If (num / 2^i) is even number, multiply result by base and do mod m
    if ((num >> i) % 2 != 0) res = (res * base) % m;
    
    // base^2 modulo m
    base = (base * base) % m;
    i++;
  }
  return res;
}
//---------------------------------------------------------------------------

template class CIntMath<char>;
template class CIntMath<short>;
template class CIntMath<int>;
template class CIntMath<long>;
template class CIntMath<unsigned char>;
template class CIntMath<unsigned short>;
template class CIntMath<unsigned int>;
template class CIntMath<unsigned long>;
template class CIntMath<CBigInt>;
